Several prior references that provide background are listed below and their contents are incorporated herein by reference in their entireties as background information. Additional references are mentioned in the above-referenced U.S. Ser. No. 61/202,022 and their contents are incorporated herein by reference in their entireties.    [1] A N, X., AND PELLACINI, F. 2008. Appprop: all-pairs appearance-space edit propagation. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 1-9.    [2] BARASH, D., AND COMANICIU, D. 2004. A common framework for nonlinear diffusion, adaptive smoothing, bilateral filtering and mean shift. Image and Video Computing 22, 73-81.    [3] BLACK, M. J., SAPIRO, G., MARIMONT, D. H., AND HEEGER, D. 1998. Robust anisotropic diffusion. Image Processing, IEEE Transactions on 7, 3, 421-432.    [4] BURRUS, C., GOPINATH, R., AND GUO, H. 1998. Introduction to Wavelets and Wavelet Transforms, A Primer. Prentice Hall, N.J.    [5] BURT, P. J., AND ADELSON, E. H. 1983. The laplacian pyramid as a compact image code. IEEE Transactions on CommunicationsCOM-31, 4, 532-540.    [6] BURT, P. J. 1981. Fast filter transforms for image processing. Proc. SPIE 2825, vol. 16, 396-408.    [7] CHAN, T. F., OSHER, S., AND SHEN, J. 2001. The digital TV filter and nonlinear denoising. IEEE Trans. Image Process 10, 231-241.    [8] CHOUDHURY, P., AND TUMBLIN, J. 2005. The trilateral filter for high contrast images and meshes. In ACM SIGGRAPH Courses, ACM, New York, N.Y., USA, 5.    [9] COHEN, A., AND MASSON, R. 1999. Wavelet methods for second-order elliptic problems, preconditioning, and adaptivity. SIAM J. Sci. Comput. 21, 3, 1006-1026.    [10] COHEN, A., DAUBECHIES, I., AND FEAUVEAU, J. C. 1992. Biorthogonal bases of compactly supported wavelets.    [11] DAHMEN, W. 1994. Some remarks on multiscale transformations, stability and bi-orthogonality. In Wavelets, Images, and Surface Fitting, Academic Press, 157-188.    [12] DONOHO, D. L. 1994. On minimum entropy segmentation. Tech. rep., Preprint: Departement of Statistics, Standford University, Stanford, Calif., 1994.    [13] DURAND, F., AND DORSEY, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 257-266.    [14] FARBMAN, Z., FATTAL, R., LISCHINSKI, D., AND SZELISKI, R. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM Trans. Graph. 27, 3, 1-10.    [15] FATTAL, R., LISCHINSKI, D., AND WERMAN, M. 2002. Gradient domain high dynamic range compression. In ACM Trans. Graph., ACM, New York, N.Y., USA, 249-256.    [16] FATTAL, R., AGRAWALA, M., AND RUSINKIEWICZ, S. 2007. Multiscale shape and detail enhancement from multi-light image collections. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 51.    [17] FATTAL, R., CARROLL, R., AND AGRAWALA, M. 2009. Edge-based image coarsening. Tech. rep., Leibniz Center, Hebrew University, URL http://leibniz.cs.huji.ac.il/tr/1147.pdf.    [18] FATTAL, R. 2008. Single image dehazing. ACM Trans. Graph. 27, 3, 1-9.    [19] FINLAYSON, G. D., HORDLEY, S. D., DREW, M. S., AND T J, E. N. 2002. Removing shadows from images. In In ECCV 2002: European Conference on Computer Vision, 823-836.    [20] FLEISHMAN, S., DRORI, I., AND COHEN-O R, D. 2003. Bilateral mesh denoising. ACM Trans. Graph. 22, 3, 950-953.    [21] GONZALEZ, R. C., AND WOODS, R. E. 2001. Digital Image Processing. Addison-Wesley Longman Publishing Co., Inc., Boston, Mass., USA.    [22] GORTLER, S. J., SCHRÖDER, P., COHEN, M. F., AND HANRAHAN, P. 1993. Wavelet radiosity. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 221-230.    [23] GORTLER, S. J., GRZESZCZUK, R., SZELISKI, R., AND COHEN, M. F. 1996. The lumigraph. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 43-54.    [24] HARTEN, A. 1996. Multiresolution representation of data: a general framework. SIAM J. Numer. Anal. 33, 3, 1205-1256.    [25] KHAN, E. A., REINHARD, E., FLEMING, R. W., AND BÜLTHOFF, H. H. 2006. Image-based material editing. ACM Trans. Graph. 25, 3, 654-663.    [26] LAGENDIJK, R. L., BIEMOND, J., AND BOEKEE, D. E. 1988. Regularized iterative image restoration with ringing reduction. Acoustics, Speech, and Signal Processing [see also IEEE Transactions on Signal Processing], IEEE Transactions on 36, 12, 1874-1888.    [27] LEVIN, A., LISCHINSKI, D., AND WEISS, Y. 2004. Colorization using optimization. ACM Trans. Graph. 23, 3, 689-694.    [28] LI, Y., SHARAN, L., AND ADELSON, E. H. 2005. Compressing and companding high dynamic range images with subband architectures. ACM Trans. Graph. 24, 3, 836-844.    [29] LI, Y., ADELSON, E. H., AND AGARWALA, A. 2008. Scribbleboost: Adding classification to edge-aware interpolation of local image and video adjustments. Comput. Graph. Forum 27, 4, 1255-1264.    [30] LISCHINSKI, D., FARBMAN, Z., UYTTENDAELE, M., AND SZELISKI, R. 2006. Interactive local adjustment of tonal values. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 646-653.    [31] LOUNSBERY, M., DEROSE, T. D., AND WARREN, J. 1997. Multiresolution analysis for surfaces of arbitrary topological type. ACM Trans. Graph. 16, 1, 34-73.    [32] MALLAT, S. 1999. A Wavelet Tour of Signal Processing, Second Edition (Wavelet Analysis & its Applications). Academic Press, September.    [33] PARIS, S., AND DURAND, F. 2006. A fast approximation of the bilateral filter using a signal processing approach. In Proceedings of the European Conference on Computer Vision, 568-580.    [34] PELLACINI, F., AND LAWRENCE, J. 2007. Appwand: editing measured materials using appearance-driven optimization. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 54.    [35] PEREZ, P., GANGNET, M., AND BLAKE, A. 2003. Poisson image editing. ACM Trans. Graph. 22, 3, 313-318.    [36] PERONA, P., AND MALIK, J. 1990. Scale-space and edge detection using anisotropic diffusion. vol. PAMI-12, 629-639.    [37] PETSCHNIGG, G., SZELISKI, R., AGRAWALA, M., COHEN, M., HOPPE, H., AND TOYAMA, K. 2004. Digital photography with flash and no-flash image pairs. ACM Trans. Graph. 23, 3, 664-672.    [38] SCHLICK, C. 1994. Quantization techniques for visualization of high dynamic range pictures. Springer-Verlag, 7-20.    [39] SCHRÖDER, P., AND SWELDENS, W. 1995. Spherical wavelets: efficiently representing functions on the sphere. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 161-172.    [40] SHEN, J., JIN, X., ZHOU, C., AND WANG, C. C. L. 2007. Technical section: Gradient based image completion by solving the Poisson equation. Comput. Graph. 31, 1, 119-126.    [41] SORKINE, O., COHEN-OR, D., LIPMAN, Y., ALEXA, M., RÖSSL, C., AND SEIDEL, H.-P. 2004. Laplacian surface editing. In SGP '04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, ACM, New York, N.Y., USA, 175-184.    [42] SUN, J., JIA, J., TANG, C.-K., AND SHUM, H.-Y. 2004. Poisson matting. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 315-321.    [43] SWELDENS, W. 1995. The lifting scheme: A new philosophy in biorthogonal wavelet constructions. In in Wavelet Applications in Signal and Image Processing III, 68-79.    [44] SWELDENS, W. 1998. The lifting scheme: a construction of second generation wavelets. SIAM J. Math. Anal. 29, 2, 511-546.    [45] SZELISKI, R. 2006. Locally adapted hierarchical basis preconditioning. In ACM SIGGRAPH papers, ACM, New York, N.Y., USA, 1135-1143.    [46] TOMASI, C., AND MANDUCHI, R. 1998. Bilateral filtering for gray and color images. In ICCV '98: Proceedings of the Sixth International Conference on Computer Vision, IEEE Computer Society, Washington, D.C., USA, 839.    [47] TUMBLIN, J., AND TURK, G. 1999. Lcis: a boundary hierarchy for detail-preserving contrast reduction. In ACM SIGGRAPH papers, ACM Press/Addison-Wesley Publishing Co., New York, N.Y., USA, 83-90.    [48] UYTTERHOEVEN, G., ROOSE, D., AND BULTHEEL, A. 1999. Integer wavelet transforms using the lifting scheme. World Scientific and Engineering Society Press, 198-200.    [49] WEISS, Y. 2001. Deriving intrinsic images from image sequences. Computer Vision, IEEE International Conference on 2, 68.
Filtering lies behind almost every operation on digital images. Explicit linear translation-invariant (LTI) filtering, i.e., convolution, is used extensively in a wide range of applications which include noise removal, resolution enhancement and reduction, blurring and sharpening, edge detection, and image compression [Gonzalez and Woods 2001]. Data-dependent filtering with, e.g., the bilateral filter [Tomasi and Manduchi 1998], adjusts filter stencils at each pixel based on the pixel's surrounding. In this robust filtering, pixels across edges are not averaged together, thereby avoiding edge-related halo artifacts that plague many image operations that rely on LTI filtering. In addition, switching to such data-dependent filtering requires little or no further algorithmic modifications, making it very poplar in computational photography.
Both the LTI and data-dependent filtering can be used in implicit formulations, where the unknown image appears convolved, allowing images to be defined through their filtering. The gradient domain [Weiss 2001; Fattal et al. 2002; Pérez et al. 2003] processing, where images are computed from their derivatives, is one popular example for implicit translation-invariant filtering. This approach provides a transparent way of manipulating edges in the image without worrying about the global adjustments involved, but comes at the cost of solving a Poisson equation. As discussed below, the inhomogeneous Laplace and Poisson equations can be interpreted as an implicit formulation of data-dependent filtering in which requirements over the image derivatives are weighted based on the input datum. These formulations prove to be useful for edge-aware interpolation of sparse user input and as high-quality edge-preserving smoothing operators, but require solving poorly conditioned systems of equations.
Multi-resolution analysis (MRA) via wavelet transform [Burrus et al. 1998; Mallat 1999] is widely known as an extremely effective and efficient tool for LTI multi-scale decomposition and processing which provides a good localization trade-off in space and frequency. More specifically, efficient filtering with effective kernel size proportional to the image dimensions [Burt 1981], detecting edges both in space and scale [Burt and Adelson 1983], bypassing the need for implicit LTI formulations and avoiding the associated costs of solving large linear systems [Li et al. 2005], and preconditioning these systems [Cohen and Masson 1999], are all achieved in linear-time computations. In contrast to these results, data-dependent filtering requires performing O(N logN) operations in the number of image pixels N since subsampling is avoided [Fattal et al. 2007], solving multiple linear systems [Farbman et al. 2008], coping with the resulting poorly-conditioned systems [Szeliski 2006], or introducing additional dimensions and their discretization [Paris and Durand 2006].
Explicit LTI filtering is used in numerous image processing applications, see [Gonzalez and Woods 2001] for a good survey. Implicit formulations allow one to define the image through its filtering, e.g., the derivatives, and require solving systems of linear equations, e.g., Poisson equation. This is used for shadow removal [Weiss 2001; Finlayson et al. 2002], dynamic-range compression [Fattal et al. 2002], seamless image editing [Pérez et al. 2003], image completion [Shen et al. 2007], alpha matting [Sun et al. 2004], and surface editing [Sorkine et al. 2004].
Data-dependent filtering such as the bilateral filter [Tomasi and Manduchi 1998] adjusts the weight of each pixel based on its distance, both in space and intensity, from the center pixel. This operation is not linear and does not correspond to filtering in the strict sense of the word; however it serves the same purpose as its linear counterpart: both operations target the data through a prescribed localization in space and frequency, i.e., they can blur the image or extract its fine-scale detail. Other prototypical approaches for data-dependent filtering include anisotropic diffusion [Perona and Malik 1990], robust smoothing [Black et al. 1998], and digital total variation [Chan et al. 2001]. In the past two decades or so, these filters became very popular for their ability to smooth an image while keeping its salient edges intact, and are known as edge-preserving smoothing filters. One of the main advantages of this property is avoiding the well-known halo artifacts which are typical to image operations that rely on linear filtering. Edge-preserving smoothing is used in numerous computational photography applications such as smoothing color images [Tomasi and Manduchi 1998], edge-preserving noise removal [Chan et al. 2001; Choudhury and Tumblin 2005], dynamic-range compression [Tumblin and Turk 1999; Durand and Dorsey 2002], flash and no-flash photography [Petschnigg et al. 2004], image editing [Khan et al. 2006], and mesh denoising [Fleishman et al. 2003].
Data-dependent filtering also has an implicit counterpart, the inhomogeneous Laplace and Poisson equations. As shown in [Farbman et al. 2008], the inhomogeneous Poisson equation expresses the steady-state condition of linear anisotropic diffusion processes and therefore acts as an edge-preserving smoothing operator. Much like the analogy between LTI filtering and Poisson-based image generation, the inhomogeneous Laplace and Poisson equations compute a least squares solution over weighted image derivatives [Farbman et al. 2008] and can therefore be regarded as a weighted filtering of the output image. This is used also for regulating deblurring operation of noisy images [Lagendijk et al. 1988], manipulating the detail and contrast of images [Farbman et al. 2008], and regulating estimated transmission in hazy scenes [Fattal 2008]. A similar formalism is used for image colorization [Levin et al. 2004] and tonal adjustment [Lischinski et al. 2006] methods, where sparse user strokes of color or adjustment parameters are propagated across the image in an edge-aware fashion. This results in a spatially-dependent Laplace equation and as used for other applications such as material [Pellacini and Lawrence 2007] and appearance [An and Pellacini 2008] editing, and in [Li et al. 2008] this edge-aware interpolation is boosted via a classification step.
Traditional MRA [Mallat 1999; Burrus et al. 1998] is, in its essence, a linear translation-invariant filtering. This results from a uniform notion of smoothness throughout space, defined by a single pair of scaling and wavelet functions, and reveals itself as the convolution in the wavelet transform equations. While this analysis excels in separating weak variations based on their scale, it fails to isolate large-magnitude jumps in the data such as the ones encountered across edges. As indicated in previous reports [Schlick 1994; Tumblin and Turk 1999; Li et al. 2005; Farbman et al. 2008], strong edges respond to filters at several scales thus producing multiple ‘reads’ in multi-scale decomposition. Processing the different scales independently often violates the delicate relationships within this multiplicity and results in haloing and other artifacts around strong edges in the reconstructed image [Tumblin and Turk 1999]. Avoiding these artifacts, in the framework of LTI decompositions, requires taking special precautions when processing the different bands [Li et al. 2005].
Very recently, several multi-scale constructions have been proposed in the context of data-dependent image filtering. Paris et al. [2006] exploit the facts that the bilateral filter is an LTI filter in the extended neighborhood, consisting of space and pixel-intensity range [Barash and Comaniciu 2004] and that linear filtering can be computed efficiently through a multi-level strategy [Burt 1981], to achieve a linear-time implementation of bilateral filtering with arbitrarily large kernels. This comes at a storage cost where an additional dimension (intensity range) must be discretized (or three in case of color images). A multi-scale decomposition, based on the dyadic wavelet transform [Mallat 1999] and bilateral filter, is proposed in [Fattal et al. 2007] and operates in O(N logN) time. This decomposition runs the bilateral filter repeatedly and results in oversharpened edges that persist in the coarsest scales. This may lead to gradient reversals when used for image processing [Farbman et al. 2008]. Farbman et al. [2008] show that the weighted least squares, i.e., inhomogeneous Poisson equation, can be used for computing edge-preserving smoothing at multiple scales. This approach requires solving large numerically-challenging linear systems for each scale. Szeliski proposes a locally-adapted hierarchical basis for preconditioning this type of linear systems. More recently, Fattal et al. [2009] propose an adaptive edge-based image coarsening for tone-mapping operations. In this approach the image is represented by fewer degrees of freedom than the original number of pixels. While it avoids certain bleeding artifacts, this reduced representation supports a limited number of image operations. For example, it does not provide a scale separation and cannot be used to manipulate image details.